

e = 0x10001
c= 9949542934673249601822379710110536682375274333294212429688584989332571435120688962792756767799023906332576991820877786082142174075762351091472858450420524999000438499038246804892307015253501997557003507879115010365751701766309706931191167213901685725286428926861333201965004869326873632404052661985741631906479109023390455968199954361183959446992180809970004376995201084933073767278979855530735756096072840384641334181432769063314242300512881491103946010394543208395998872730145780806025267971492301568490427293141120807461902093932052106811061648537600125019831876736538658644780471805555396705702634885360657660235
n= 14775235844515544576473611382698284004133861994231391972299917039113871334718108546717938305388267655285590882177982603418940337565701637106925368292676630781520319110700106306029357476649553934570683454139537943486518666101218072140043084858740684805876092240053196287287330188619164273915005792335974297620475140547828827559062269649682393716241864595363863867012095487700403514116433664086346056485373014640655316422588972338531776150881686013955605480910803097642414475309381073364181798620439167561641939844350252283317699576359402716770493658380425200603092475286870303441165147435503582004675788584686434009043

import gmpy2
import libnum

a=gmpy2.iroot(n,2)[0]
lt=[]
while 1:
    a+=1
    b2=pow(a,2)-n
    if gmpy2.is_square(b2):
        tmp=[]
        b=gmpy2.iroot(b2,2)[0]
        x1=a-b
        x2=a+b
        tmp.append(int(x1))
        tmp.append(int(x2))
        lt.append(tmp)
    if len(lt)>=2:
        break
print(lt)
assert lt[0][1]*lt[0][0]==n
assert lt[1][1]*lt[1][0]==n
p=libnum.gcd(lt[0][0],lt[1][0])
print(p)
print(gmpy2.is_prime(p))
p1=gmpy2.next_prime(p)
print(p1)
q=libnum.gcd(lt[0][1],lt[1][0])
print(q)
print(gmpy2.is_prime(q))
q1=gmpy2.next_prime(q)
print(q1)
print(n==p*p1*q*q1)
phi=(p-1)
d=libnum.invmod(e,phi)
m=pow(c,d,p)
print(libnum.n2s(int(m)))
